package interview.Algorithms;

import java.util.ArrayList;
import java.util.Iterator;

public class Dijkstra {
	
	
	class vertexDistance{
		int distance;
		Edge reachable ;
		public vertexDistance (){
			distance = Integer.MAX_VALUE;
			reachable = null;					
		}
		
		public int getDistance() {
			return distance;
		}
		public void setDistance(int distance) {
			this.distance = distance;
		}
		public Edge getReachable() {
			return reachable;
		}
		public void setReachable(Edge reachable) {
			this.reachable = reachable;
		} 		
		
		public String toString(){
			return "  "+ distance + "   "+  reachable; 
		}
	}
	
	
	@SuppressWarnings("unused")
	public Iterable<Edge> shortestDistance(Graph graph,int startPos){
		ArrayList<Edge> mstEdge = new ArrayList<Edge>();
		boolean[] vertexAdded =new boolean[graph.getVertices()];
		vertexDistance[] vertexCalculated = new vertexDistance[graph.getVertices()];		
	
		for(int i=0;i<vertexCalculated.length;i++)
			vertexCalculated[i]=new vertexDistance();
		
		int vertexSeen = 1;
		int predWeight = 0;
		vertexAdded[startPos]= true;
		Iterator<Edge> edges = null; 
		MinPriorityQueue<Edge> pq = new MinPriorityQueue<>(graph.getEdges());
		Edge edgeAdded = null;
		int currentVertex = startPos;
		while (true){
			edges = (graph.getVertexInfo(currentVertex).getEdges());     
			while(edges.hasNext()){
				Edge tempEdge = (Edge)edges.next();
				
				if (!tempEdge.isVisited()){
					tempEdge.setVisited(true);
					int prevVertex= tempEdge.getAnotherVertex(currentVertex);				
					
				/*	if(vertexCalculated[prevVertex]==null){
						vertexCalculated[prevVertex].setDistance(tempEdge.getWeight());
						vertexCalculated[prevVertex].setReachable(tempEdge);
					}					
				*/	
					int prevDistance = vertexCalculated[prevVertex].getDistance();
					int currentDistance = predWeight + tempEdge.getWeight();
				
					if(prevDistance>currentDistance){
						vertexCalculated[prevVertex].setReachable(tempEdge);
						vertexCalculated[prevVertex].setDistance(currentDistance);
					}
					pq.insert(tempEdge);
				}
			}
			
			if(pq.isEmpty())break;
			edgeAdded = (Edge)pq.deleteMin();
			mstEdge.add(edgeAdded);			
			vertexAdded[currentVertex]=true;

			vertexSeen++;
			if(vertexAdded[edgeAdded.getU()]) 
				currentVertex = edgeAdded.getV();			
			else
				currentVertex=edgeAdded.getU();
			
			predWeight = vertexCalculated[currentVertex].getDistance();		
		}
		
		for(int i=0;i<vertexCalculated.length;i++)
			System.out.println(vertexCalculated[i]);
		
		
		return mstEdge;		
	}
}
